1. Field of Invention
This invention relates to iterative decoding of input sequences.
2. Description of Related Art
Maximum a posteriori (MAP) sequence decoding selects a most probable information sequence X1T=(X1, X2, . . . , XT) that produced the received sequence Y1T=(Y1, Y2, . . . , YT). For transmitters and/or channels that are modeled using Hidden Markov Models (HMM), the process for obtaining the information sequence X1T that corresponds to a maximum probability is difficult due to a large number of possible hidden states as well as a large number of possible information sequences X1T. Thus, new technology is needed to improve MAP decoding for HMMs.
This invention provides an iterative process to maximum a posteriori (MAP) decoding. The iterative process uses an auxiliary function which is defined in terms of a complete data probability distribution. The MAP decoding is based on an expectation maximization (EM) algorithm which finds the maximum by iteratively maximizing the auxiliary function. For a special case of trellis coded modulation, the auxiliary function may be maximized by a combination of forward-backward and Viterbi algorithms. The iterative process converges monotonically and thus improves the performance of any decoding algorithm.
The MAP decoding decodes received inputs by minimizing a probability of error. A direct approach to achieve this minimization results in a complexity which grows exponentially with T, where T is the size of the input. The iterative process avoids this complexity by converging on the MAP solution through repeated use of the auxiliary function.